home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 5988 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.1 KB  |  58 lines
  1. Newsgroups: comp.lang.c,comp.graphics.algorithms,rec.games.programmer
  2. Path: xylo.owl.de!aurel
  3. From: aurel@xylo.owl.de (Aurel Balmosan)
  4. Subject: Re: Speed question here...
  5. Followup-To: comp.lang.c,comp.graphics.algorithms,rec.games.programmer
  6. References: <4ftluh$1gkv@hearst.cac.psu.edu>
  7. Organization: Xylo-Systems
  8. Date: Wed, 21 Feb 1996 23:36:57 GMT
  9. X-Newsreader: TIN [UNIX 1.3 941216BETA PL0]
  10. Message-ID: <Dn5G9L.ss@xylo.owl.de>
  11.  
  12. William Koscho (koscho@wjk130.rh.psu.edu) wrote:
  13. : I was curious as to how fast something like the 
  14. : following would execute:
  15.  
  16. :     int x;
  17. :     node *ptr;   ptr in linked list
  18.  
  19. :        for ( ptr = first_node; ptr != NULL; ptr = ptr.next ) {
  20. :        for ( x = 0; x < max; x++ ) {
  21. :         array[x] = array_other[x];
  22. :            }
  23. :       } 
  24.  
  25. : I really am not interested in the assignment statement, that's easy.
  26. : but the traversal through the linked list, and inner integer incremental
  27. : for loop for each node visited.  How fast is a traversal through
  28. : a linked list when you do a for loop at each node?
  29.  
  30. Your code uses about O(max * Number of list elements). You can reduce this
  31. to O(Number of list elements) by involving an object-based approach.
  32.  
  33. In your code you copy an array to an other one. (I assume that this other
  34. array is a pointer within a list element). Because you copy always the
  35. same array to the other, why coping the array. Instate of copying the
  36. array you could reference this array with a pointer. So this array becomes
  37. a object of some kind. This object must be managed in the following ways:
  38. -    creation
  39. -    deletion
  40. -    copying
  41. -    duplicate if someone wants to change it and others are using
  42.     it already and they want the old state. 
  43.  
  44. This is only a small overhead but it will avoid as much copy loop as
  45. possible. 
  46.  
  47. Other approaches to speed up your code by using different command orders
  48. are very subject to the used C-compiler and the way the compiler generates
  49. assembler code. (btw: If you want very good assembler code use the GCC)
  50.  
  51.  
  52.     Aurel Balmosan
  53.  
  54. -- 
  55.  
  56. ----------------------------------------------------------------
  57. Aurel Balmosan        aurel@xylo.owl.de
  58.